{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Min Cost to Connect All Points"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #graph #array #minimum-spanning-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #图 #数组 #最小生成树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCostConnectPoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #连接所有点的最小费用"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个<code>points</code>&nbsp;数组，表示 2D 平面上的一些点，其中&nbsp;<code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>&nbsp;。</p>\n",
    "\n",
    "<p>连接点&nbsp;<code>[x<sub>i</sub>, y<sub>i</sub>]</code> 和点&nbsp;<code>[x<sub>j</sub>, y<sub>j</sub>]</code>&nbsp;的费用为它们之间的 <strong>曼哈顿距离</strong>&nbsp;：<code>|x<sub>i</sub> - x<sub>j</sub>| + |y<sub>i</sub> - y<sub>j</sub>|</code>&nbsp;，其中&nbsp;<code>|val|</code>&nbsp;表示&nbsp;<code>val</code>&nbsp;的绝对值。</p>\n",
    "\n",
    "<p>请你返回将所有点连接的最小总费用。只有任意两点之间 <strong>有且仅有</strong>&nbsp;一条简单路径时，才认为所有点都已连接。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/26/d.png\" style=\"height:268px; width:214px; background:#e5e5e5\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[0,0],[2,2],[3,10],[5,2],[7,0]]\n",
    "<strong>输出：</strong>20\n",
    "<strong>解释：\n",
    "</strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/26/c.png\" style=\"height:268px; width:214px; background:#e5e5e5\" />\n",
    "我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。\n",
    "注意到任意两个点之间只有唯一一条路径互相到达。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[3,12],[-2,5],[-4,1]]\n",
    "<strong>输出：</strong>18\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[0,0],[1,1],[1,0],[-1,1]]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[-1000000,-1000000],[1000000,1000000]]\n",
    "<strong>输出：</strong>4000000\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[0,0]]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= points.length &lt;= 1000</code></li>\n",
    "\t<li><code>-10<sup>6</sup>&nbsp;&lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li>所有点&nbsp;<code>(x<sub>i</sub>, y<sub>i</sub>)</code>&nbsp;两两不同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [min-cost-to-connect-all-points](https://leetcode.cn/problems/min-cost-to-connect-all-points/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [min-cost-to-connect-all-points](https://leetcode.cn/problems/min-cost-to-connect-all-points/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0],[2,2],[3,10],[5,2],[7,0]]', '[[3,12],[-2,5],[-4,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        # minimum spanning tree + union find (to determine cycles)\n",
    "        rep = {i:i for i in range(len(points))}\n",
    "        def find(x):\n",
    "            if x != rep[x]:\n",
    "                rep[x] = find(rep[x])\n",
    "            return rep[x]\n",
    "        def union(x,y):\n",
    "            rep[find(y)] = find(x)\n",
    "        edges = {}\n",
    "        ans = 0\n",
    "        numConnectedEdges = 0\n",
    "        for i in range(len(points)-1):\n",
    "            for j in range(i+1, len(points)):\n",
    "                edges[(i,j)] = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])\n",
    "        edges = dict(sorted(edges.items(), key=lambda item: item[1]))\n",
    "        for key, value in edges.items():\n",
    "            if find(key[0]) != find(key[1]):\n",
    "                ans += value\n",
    "                union(key[0],key[1])\n",
    "                numConnectedEdges += 1\n",
    "                if numConnectedEdges == len(points) - 1:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        # Prim算法\n",
    "        n = len(points)\n",
    "        distance = [float('inf')] * n \n",
    "        visited = [False] * n\n",
    "        distance[0] = 0\n",
    "        res = 0\n",
    "        for _ in range(n):\n",
    "            m = float('inf')\n",
    "            for i in range(n):\n",
    "                if not visited[i] and distance[i] < m:\n",
    "                    node = i\n",
    "                    m = distance[i]\n",
    "            visited[node] = True\n",
    "            res += m\n",
    "            for i in range(n):\n",
    "                if not visited[i]:\n",
    "                    distance[i] = min(distance[i], abs(points[i][0] - points[node][0]) + abs(points[i][1] - points[node][1]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjointSetUnion:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.rank = [1]*n\n",
    "        self.f = list(range(n))\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.f[x] == x:\n",
    "            return x\n",
    "        self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    \n",
    "    def Union(self, x1, x2):\n",
    "        root1, root2 = self.find(x1), self.find(x2)\n",
    "        if root1 == root2:\n",
    "            return False\n",
    "        if self.rank[root1] < self.rank[root2]:\n",
    "            self.f[root1] = root2\n",
    "        elif self.rank[root1] > self.rank[root2]:\n",
    "            self.f[root2] = root1\n",
    "        else:\n",
    "            self.f[root2] = root1\n",
    "            self.rank[root1] += 1\n",
    "        return True\n",
    "        \n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        # dist = lambda x,y: abs(points[x][0]-points[y][0])+abs(points[x][1]-points[y][1])\n",
    "\n",
    "        # n = len(points)\n",
    "        # dsu = DisjointSetUnion(n)\n",
    "        # edges = list()\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+1, n):\n",
    "        #         edges.append((dist(i,j), i, j))\n",
    "        \n",
    "        # edges.sort()\n",
    "\n",
    "        # ret, num = 0, 1\n",
    "        # for length, x, y in edges:\n",
    "        #     if dsu.Union(x, y):\n",
    "        #         ret += length\n",
    "        #         num += 1\n",
    "        #         if num == n:\n",
    "        #             break\n",
    "\n",
    "        # return ret\n",
    "\n",
    "        # dist = lambda x,y: abs(points[x][0]-points[y][0])+abs(points[x][1]-points[y][1])\n",
    "        # if not points:\n",
    "        #     return 0\n",
    "        # size = len(points)\n",
    "        # pq = PriorityQueue()\n",
    "        # visited = [False] * size\n",
    "        # result = 0\n",
    "        # count = size - 1\n",
    "        # for j in range(size):\n",
    "        #     pq.put((dist(0,j), 0, j))\n",
    "        # visited[0] = True\n",
    "\n",
    "        # while pq and count > 0:\n",
    "        #     e = pq.get()\n",
    "        #     pointX = e[1]\n",
    "        #     pointY = e[2]\n",
    "        #     cost = e[0]\n",
    "        #     if not visited[pointY]:\n",
    "        #         result += cost\n",
    "        #         visited[pointY] = True\n",
    "        #         for j in range(size):\n",
    "        #             if not visited[j]:\n",
    "        #                 pq.put((dist(pointY, j), pointY, j))\n",
    "        #         count -= 1\n",
    "        # return result\n",
    "        dist = lambda x,y: abs(points[x][0]-points[y][0])+abs(points[x][1]-points[y][1])\n",
    "        size = len(points)\n",
    "        d = [float('inf')]*size\n",
    "        visited = [False] * size\n",
    "        d[0] = 0\n",
    "        ans = 0\n",
    "        for _ in range(size):\n",
    "            M = float('inf')\n",
    "            for i in range(size):\n",
    "                if not visited[i] and d[i] < M:\n",
    "                    node = i\n",
    "                    M = d[i]\n",
    "            visited[node] = True\n",
    "            ans += M\n",
    "            for i in range(size):\n",
    "                if not visited[i]:\n",
    "                    d[i] = min(d[i], dist(i, node))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n:int) -> None:\n",
    "        self.n = n\n",
    "        self.tree = [inf] * n\n",
    "        self.iRes = [0] * n\n",
    "        self.lowbits = lambda x : x & (-x)\n",
    "    \n",
    "    def query(self, pos:int):\n",
    "        minVal, j = inf, -1\n",
    "        while pos < self.n:\n",
    "            if minVal > self.tree[pos]:\n",
    "                minVal = self.tree[pos]\n",
    "                j = self.iRes[pos]\n",
    "            pos += self.lowbits(pos)\n",
    "        return j\n",
    "    \n",
    "    def update(self, pos:int, val:int, iRec:int):\n",
    "        while pos > 0:\n",
    "            if self.tree[pos] > val:\n",
    "                self.tree[pos] = val\n",
    "                self.iRes[pos] = iRec\n",
    "            pos -= self.lowbits(pos)\n",
    "    \n",
    "class UnionSet:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "    \n",
    "    def find(self, fx:int):\n",
    "        if self.parent[fx] == fx:\n",
    "            return fx\n",
    "        self.parent[fx] = self.find(self.parent[fx])\n",
    "        return self.parent[fx]\n",
    "    \n",
    "    def union(self, fx:int, fy:int):\n",
    "        fx, fy = self.find(fx), self.find(fy)\n",
    "        if fx == fy:\n",
    "            return False\n",
    "        if self.rank[fx] < self.rank[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.rank[fx] += self.rank[fy]\n",
    "\n",
    "        self.parent[fy] = fx\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        edges = []\n",
    "        def build(pos:list[tuple]):\n",
    "            pos.sort()\n",
    "            a = [y - x for x, y, _ in pos]\n",
    "            b = sorted(set(a))\n",
    "            n = len(a)\n",
    "            bit = BIT(len(b) + 1)\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                poss = bisect.bisect(b, a[i])\n",
    "                j = bit.query(poss)\n",
    "                if j != -1:\n",
    "                    dis = abs(pos[i][0] - pos[j][0]) + abs(pos[i][1] - pos[j][1])\n",
    "                    edges.append((dis, pos[i][2], pos[j][2]))\n",
    "                bit.update(poss, pos[i][0] + pos[i][1], i)\n",
    "        \n",
    "        def resolve():\n",
    "            pos1 = [(x, y, i) for i, (x, y) in enumerate(points)]\n",
    "            build(pos1)\n",
    "            pos2 = [(y, x, i) for i, (x, y) in enumerate(points)]\n",
    "            build(pos2)\n",
    "            pos3 = [(x, -y, i) for i, (x, y) in enumerate(points)]\n",
    "            build(pos3)\n",
    "            pos4 = [(-y, x, i) for i, (x, y) in enumerate(points)]\n",
    "            build(pos4)\n",
    "        resolve()\n",
    "        edges.sort()\n",
    "        union = UnionSet(len(points))\n",
    "        ret = 0\n",
    "        for length, a, b in edges:\n",
    "            if union.union(a, b):\n",
    "                ret += length\n",
    "        return ret\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def manhattan_distance(p1: List[int], p2: List[int]) -> int:\n",
    "    # 计算曼哈顿距离，即两点之间的横向和纵向距离之和\n",
    "    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)  # 点的总数\n",
    "        visited = [False] * n  # 记录点是否被访问过的布尔数组\n",
    "        heap_dict = {0: 0}  # 用于记录每个点到当前生成树的最小距离的字典，初始将点0放入，距离为0\n",
    "        min_heap = [(0, 0)]  # 最小堆，存放 (距离, 点索引) 的元组\n",
    "        \n",
    "        mst_weight = 0  # 最小生成树的总权重\n",
    "        \n",
    "        while min_heap:\n",
    "            w, u = heappop(min_heap)  # 从最小堆中取出当前距离最小的点的信息\n",
    "            \n",
    "            # 如果点已经被访问过或者点的最小距离已经更新，则跳过\n",
    "            if visited[u] or heap_dict.get(u, float('inf')) < w:\n",
    "                continue\n",
    "            \n",
    "            visited[u] = True  # 将当前点标记为已访问\n",
    "            mst_weight += w  # 更新最小生成树的总权重\n",
    "            \n",
    "            # 遍历所有点，找到新的最小距离并将其放入堆中\n",
    "            for v in range(n):\n",
    "                if not visited[v]:\n",
    "                    new_distance = manhattan_distance(points[u], points[v])  # 计算点 u 到点 v 的曼哈顿距离\n",
    "                    \n",
    "                    if new_distance < heap_dict.get(v, float('inf')):\n",
    "                        heap_dict[v] = new_distance  # 更新点 v 的最小距离\n",
    "                        heappush(min_heap, (new_distance, v))  # 将点 v 加入堆中\n",
    "        \n",
    "        return mst_weight  # 返回最小生成树的总权重\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        # 由于边的数目较多，应该用prim算法\n",
    "        n = len(points)\n",
    "        W = [] # j must > i,Weight[i][j] = W[i][j-i] \n",
    "        for i in range(n) :\n",
    "            tmp = [0]\n",
    "            for j in range(i+1,n) :\n",
    "                tmp.append(abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])) \n",
    "            W.append(tmp)\n",
    "        D = [float(\"inf\")]*n\n",
    "        D[0] = 0\n",
    "        visited = [False]*n\n",
    "        visited[0] = True\n",
    "        min_j = 0\n",
    "        for i in range(n) :\n",
    "            w = W[i][min_j-i] if i <= min_j else W[min_j][i-min_j] \n",
    "            D[i] = w if w<D[i] else D[i]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n-1) : \n",
    "            min_j = -1\n",
    "            min_val = float(\"inf\") \n",
    "            for j in range(n) : # 找最小距离的点加入U \n",
    "                if not visited[j] and D[j]<min_val :\n",
    "                    min_j,min_val = j,D[j]\n",
    "            res += min_val # 更新距离矩阵及res\n",
    "            visited[min_j] = True\n",
    "            for k in range(n) : \n",
    "                w = W[k][min_j-k] if k <= min_j else W[min_j][k-min_j] \n",
    "                D[k] = w if w<D[k] else D[k] \n",
    "        return res\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        V=len(points)\n",
    "        graph=[ [0]*V for i in range(0,V) ] \n",
    "        for i in range(0,V-1):\n",
    "            for j in range(i+1,V):\n",
    "                graph[i][j]=graph[j][i]=abs(points[i][0] - points[j][0])+abs(points[i][1] - points[j][1])\n",
    "        return self.prim(graph)\n",
    "    def prim(self,graph: List[List[int]]):\n",
    "        def minKey(key,mstSet,V):\n",
    "            minV=float('inf')\n",
    "            minIndex=-1\n",
    "            for v in range(0,V):\n",
    "                if( not mstSet[v] and key[v]<minV ):\n",
    "                    minV=key[v]\n",
    "                    minIndex=v\n",
    "            return minIndex\n",
    "\n",
    "        V=len(graph)\n",
    "        parent=[0]*V\n",
    "        key=[float('inf')]*V\n",
    "        key[0]=0\n",
    "        parent[0]=-1\n",
    "        mstSet=[False]*V\n",
    "        for cnt in range (0,V-1):\n",
    "            u=minKey(key,mstSet,V)\n",
    "            mstSet[u]=True\n",
    "            for v in range (0,V):\n",
    "                if (graph[u][v] and not mstSet[v] and graph[u][v]<key[v]):\n",
    "                    parent[v]=u\n",
    "                    key[v]=graph[u][v]\n",
    "        ret=0\n",
    "        for i in range(1,V):\n",
    "            ret+=graph[parent[i]][i]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        distance = [10**9]*n\n",
    "        edges = [[0]*n for _ in range(n)]\n",
    "        visited = [False]*n\n",
    "        index=0\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                temp = abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])\n",
    "                edges[i][j] = temp\n",
    "                edges[j][i] = temp\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if visited[j] == False:\n",
    "                    if edges[index][j]<distance[j]:\n",
    "                        distance[j] = edges[index][j]\n",
    "            min_val = 10**9\n",
    "            for j in range(n):\n",
    "                if distance[j]<min_val:\n",
    "                    min_val = distance[j]\n",
    "                    index = j\n",
    "            res += min_val\n",
    "            distance[index] = 10**9\n",
    "            visited[index] = True\n",
    "        return res\n",
    "            \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        visited = [0] * n\n",
    "        lowcost = [float('Inf')] * n\n",
    "        distance = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])\n",
    "                distance[i][j] = dist\n",
    "                distance[j][i] = dist\n",
    "        visited[0] = 1\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            lowcost[i] = distance[i][0]\n",
    "        for i in range(1, n):\n",
    "            minIndex = -1\n",
    "            minVal = float('Inf')\n",
    "            for j in range(n):\n",
    "                if visited[j] == 0 and lowcost[j] < minVal:\n",
    "                    minVal = lowcost[j]\n",
    "                    minIndex = j \n",
    "            visited[minIndex] = 1\n",
    "            res += minVal\n",
    "            # update lowcost for remaining points\n",
    "            for j in range(n):\n",
    "                if visited[j] == 0 and distance[j][minIndex] < lowcost[j]:\n",
    "                    lowcost[j] = distance[j][minIndex]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        graph = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                pi,pj = points[i],points[j]\n",
    "                cost = abs(pi[0]-pj[0])+abs(pi[1]-pj[1])\n",
    "                graph[i][j] = graph[j][i] = cost \n",
    "        q = [(0,0)]\n",
    "        vist = [0]*n\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        res = 0\n",
    "        while q:\n",
    "            cost,point = heapq.heappop(q)\n",
    "            if vist[point]: continue\n",
    "            vist[point] = 1\n",
    "            res += cost\n",
    "            for nex,nexcost in enumerate(graph[point]):\n",
    "                if nex != point and dist[nex] > nexcost:\n",
    "                    dist[nex] = nexcost\n",
    "                    heapq.heappush(q,(dist[nex],nex))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        if n<=1:\n",
    "            return 0\n",
    "        list_1 = [2**32 for i in range(n*n)]\n",
    "        z = np.asarray(list_1,dtype=int)\n",
    "        z = z.reshape(n,n)\n",
    "        for p,i in enumerate(points):\n",
    "            for q,j in enumerate(points):\n",
    "                if p<=q:\n",
    "                    pass\n",
    "                else:\n",
    "                    distant = max(i[0]-j[0],j[0]-i[0])+max(i[1]-j[1],j[1]-i[1])\n",
    "                    z[q][p] = distant\n",
    "                    z[p][q] = distant\n",
    "        res = 0\n",
    "        set_3 = {0}\n",
    "        while len(set_3) != n:\n",
    "            num = 2**32\n",
    "            for j in set_3:\n",
    "                next_index = np.argmin(z[j])\n",
    "                if z[j][next_index] < num:\n",
    "                    min_index = next_index\n",
    "                    num = z[j][next_index]\n",
    "            res += int(num)\n",
    "            for j in set_3:\n",
    "                z[j][min_index] = 2**32\n",
    "                z[min_index][j] = 2**32\n",
    "            set_3.add(min_index)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "def dist(p1, p2):\n",
    "        return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self, gra):\n",
    "        self.gra = gra\n",
    "        self.n = len(gra)\n",
    "        self.dict = {}\n",
    "        for i in range(self.n):\n",
    "            self.dict[i] = i\n",
    "\n",
    "    def link(self, p1, p2, mat):\n",
    "        rm_tree = self.dict[p2]\n",
    "        if self.dict[p1] != rm_tree:\n",
    "            self.gra[p1][p2] = mat[p1][p2]\n",
    "            for i in range(self.n):\n",
    "                if self.dict[i] == rm_tree:\n",
    "                    self.dict[i] = self.dict[p1]\n",
    "        for i in range(self.n):\n",
    "            if self.dict[i] != rm_tree:\n",
    "                return False    \n",
    "        return True\n",
    "            \n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        mat = np.ones([n, n]) * np.inf\n",
    "        gra = np.zeros([n, n])\n",
    "        for mi in range(1, n):\n",
    "            for mj in range(0, mi):\n",
    "                if mi == mj:\n",
    "                    d = np.inf\n",
    "                else: d = dist(points[mi], points[mj])\n",
    "                mat[mi, mj] = d\n",
    "\n",
    "        tree = Tree(gra)\n",
    "        while True:\n",
    "            min_id = mat.argmin()\n",
    "            min_row = min_id // n\n",
    "            min_col = min_id % n\n",
    "            min_val = mat.min()\n",
    "            # if isinf(min_val):\n",
    "            #     break\n",
    "            # else:\n",
    "            isend = tree.link(min_row, min_col, mat)\n",
    "            if isend:\n",
    "                return int(tree.gra.sum())\n",
    "            else:\n",
    "                mat[min_row][min_col] = inf\n",
    "                mat[min_col][min_row] = inf\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        v = [0] * n\n",
    "        total = 0\n",
    "        v[0] = 1\n",
    "        vc = 0\n",
    "        d = []\n",
    "        dd = [float('inf')] * n\n",
    "        dd[0] = 0\n",
    "        def dis(i,j):\n",
    "            return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])\n",
    "        for i in range(1, n):\n",
    "            dd[i] = dis(0,i)\n",
    "            heappush(d, (dd[i], i))\n",
    "        while d:\n",
    "            ds, t = heappop(d)\n",
    "            if v[t]:\n",
    "                continue\n",
    "            # print(t, total, d)\n",
    "            total += ds\n",
    "            v[t] = 1\n",
    "            vc += 1\n",
    "            if vc == n:\n",
    "                break\n",
    "            for i in range(n):\n",
    "                if not v[i]:\n",
    "                    dti = dis(t,i)\n",
    "                    if dti < dd[i]:\n",
    "                        heappush(d, (dti,i))\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: [[int]]) -> int:\n",
    "\n",
    "        point_set = set()\n",
    "        for p in points[1:]:\n",
    "            point_set.add(tuple(p))\n",
    "        res = 0\n",
    "        new_p = tuple(points[0])\n",
    "        grid = []\n",
    "\n",
    "        def cal_dis(p1, p2):\n",
    "            return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])\n",
    "\n",
    "        inf = 10 ** 7\n",
    "        while len(point_set) > 0:\n",
    "            node_dist = []\n",
    "            for p in point_set:\n",
    "                node_dist.append((cal_dis(p, new_p), p))\n",
    "            node_dist.sort(key=lambda k: k[0], reverse=True)\n",
    "            grid.append([new_p, node_dist])\n",
    "            min_index_dis = [-1, inf]\n",
    "            for i in range(len(grid)):\n",
    "                gp, node_dist = grid[i]\n",
    "                while node_dist:\n",
    "                    if node_dist[-1][1] in point_set:\n",
    "                        break\n",
    "                    else:\n",
    "                        node_dist.pop()\n",
    "                if len(node_dist) > 0 and min_index_dis[1] > node_dist[-1][0]:\n",
    "                    min_index_dis[0] = i\n",
    "                    min_index_dis[1] = node_dist[-1][0]\n",
    "\n",
    "            tmp_dist, new_p = grid[min_index_dis[0]][1].pop()\n",
    "            point_set.remove(new_p)\n",
    "            res += tmp_dist\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:#这是prim\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        costs = [[0]*n for _ in range(n)]\n",
    "        #n = len(points)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                costs[i][j] = abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])\n",
    "        dist = [0]*n\n",
    "        used = [False]*n\n",
    "        used[0] = True\n",
    "        for i in range(n):\n",
    "            dist[i] = costs[0][i]\n",
    "        ans = 0\n",
    "        for i in range(n-1):\n",
    "            x = -1\n",
    "            for y,u in enumerate(used):\n",
    "                if u==False and (x==-1 or dist[y]<dist[x]):\n",
    "                    x = y   \n",
    "            ans+=dist[x]\n",
    "            used[x] = True\n",
    "            for j in range(n):\n",
    "                dist[j] = min(dist[j],costs[x][j])#更新的是当前点到目前遍历到的这个最小点的距离,也就是到集合的距离, dij更新的是规定起始点到当前点的最小距离\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        self.ans = 0\n",
    "        vis = [False for i in range(n)]\n",
    "        dis = [[float('inf') for j in range(n)]for i in  range(n)]\n",
    "        low = [float('inf') for i in range(n)]\n",
    "        # 初始化权重\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                dis[j][i] = dis[i][j] = abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])\n",
    "        # print(dis)\n",
    "        def prim(n):\n",
    "            # 从任意一个节点开始，比如从第0个节点开始\n",
    "            pre_point = 0\n",
    "            vis[0] = True\n",
    "            for i in range(n):\n",
    "                if vis[i]:\n",
    "                    continue\n",
    "                low[i] = dis[i][0]\n",
    "            # 找到距离当前节点集距离最小的节点，并标记\n",
    "            # 循环n-1次，因为要选择剩下的n-1个节点\n",
    "            for cnt in range(n-1):\n",
    "                minValue = float('inf')\n",
    "                for i in range(n):\n",
    "                    if vis[i]:\n",
    "                        continue\n",
    "                    # print('distance is ',dis[i][pre_point])\n",
    "                    if low[i] < minValue:\n",
    "                        minValue = low[i]\n",
    "                        pre_point = i\n",
    "                # print(pre_point,minValue)\n",
    "                vis[pre_point] = True\n",
    "                self.ans += minValue\n",
    "                #print(minValue)\n",
    "                # 更新权重\n",
    "                for i in range(n):\n",
    "                    if vis[i]:\n",
    "                        continue\n",
    "                    if  low[i] > dis[i][pre_point]:\n",
    "                        low[i] = dis[i][pre_point]\n",
    "        prim(n)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def init(self,n):self.fa=[i for i in range(n)]\n",
    "    def find(self,x):\n",
    "        if x==self.fa[x]:return x\n",
    "        else:\n",
    "            self.fa[x]=self.find(self.fa[x])\n",
    "            return self.fa[x]\n",
    "    def union(self,a,b):\n",
    "        self.fa[self.find(a)]=self.find(b)\n",
    "\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        #建graph\n",
    "        m=len(points)\n",
    "        graph=[[0]*m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(m): #1) i+1:m-1 + m-2 +...+1= m*(m-1)//2 2)i: m * m\n",
    "                graph[i][j]=abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])\n",
    "\n",
    "        \n",
    "        #prim\n",
    "        q=[]\n",
    "        heapq.heappush(q,(0,0)) #dist,node\n",
    "\n",
    "        dist=[float('inf')]*m\n",
    "        vst=[False]*m\n",
    "\n",
    "        res=0\n",
    "        while q:\n",
    "            min_dist,min_id=heapq.heappop(q)\n",
    "            if vst[min_id]:continue\n",
    "            \n",
    "            vst[min_id]=True\n",
    "            res+=min_dist\n",
    "\n",
    "            for j in range(m):\n",
    "                if dist[j]>graph[min_id][j]:\n",
    "                    dist[j]=graph[min_id][j]\n",
    "                    heapq.heappush(q,(dist[j],j))\n",
    "        return res\n",
    "            \n",
    "            \n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        # 最小生成树：prim  在dijkstra上加上一些就好\n",
    "\n",
    "        g = [[] for _ in range(len(points))]\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(points)):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                g[i].append(j)\n",
    "        print(g)\n",
    "\n",
    "        dist = [float('inf') for _ in range(len(points))]\n",
    "        dist[0] = 0\n",
    "        v = [-1 for _ in range(len(points))]\n",
    "\n",
    "        queue = []\n",
    "        heapq.heappush(queue, (0, 0))\n",
    "\n",
    "        res = 0\n",
    "        while queue:\n",
    "            t, x = heapq.heappop(queue)\n",
    "\n",
    "            if dist[x] < t:\n",
    "                continue\n",
    "\n",
    "            # 每条边只选择一次\n",
    "            if v[x] == 0:\n",
    "                continue\n",
    "            \n",
    "            v[x] = 0\n",
    "            res += t\n",
    "\n",
    "            for y in g[x]:\n",
    "                dis = abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1])\n",
    "                if dis < dist[y]:\n",
    "                    dist[y] = dis\n",
    "                    heapq.heappush(queue, (dis, y))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.parent=list(range(n))\n",
    "\n",
    "    def union(self,i,j):\n",
    "        self.parent[self.find(i)]=self.find(j)\n",
    "    \n",
    "    def find(self,i):\n",
    "        if i!=self.parent[i]:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "        return self.parent[i]\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        import heapq\n",
    "        res=0\n",
    "        n=len(points)\n",
    "        tobedone=set(range(n))\n",
    "        h=[]\n",
    "        heapq.heappush(h,(0,0))#(cost,point)\n",
    "        while h:\n",
    "            w,i=heapq.heappop(h)\n",
    "            if i in tobedone:\n",
    "                tobedone.remove(i)\n",
    "                res+=w\n",
    "                for j in tobedone:\n",
    "                    heapq.heappush(h,(abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1]),j))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        '''\n",
    "        n=len(points)\n",
    "        edges={}\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                edges[(i,j)]=abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])\n",
    "        edges=sorted(edges.items(),key=lambda x:x[1])\n",
    "        res=0\n",
    "        uf=UnionFind(n)\n",
    "        for (i,j),w in edges:\n",
    "            if uf.find(i)!=uf.find(j):\n",
    "                uf.union(i,j)\n",
    "                res+=w\n",
    "        return res\n",
    "        '''\n",
    "            \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)  # 图的顶点数\n",
    "        visited = set()  # 记录顶点是否已经加入生成树\n",
    "        total_cost = 0  # 记录生成树的总权值\n",
    "        min_heap = [(0,points[0][0],points[0][1])]  # 优先队列，用于选择最小权值的边\n",
    "        while min_heap:\n",
    "            cost, x1,y1 = heapq.heappop(min_heap)\n",
    "            if (x1,y1) in visited:\n",
    "\n",
    "                continue\n",
    "            visited.add((x1,y1))\n",
    "            total_cost += cost\n",
    "            for x2,y2 in points:\n",
    "                if (x2,y2) != (x1,y1) and (x2,y2) not in visited:\n",
    "                    w = abs(x2-x1)+abs(y2-y1)\n",
    "                    heapq.heappush(min_heap, (w,x2,y2))\n",
    "            \n",
    "        return total_cost\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 排序+并查集\n",
    "from itertools import combinations\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        hq = []\n",
    "        for i, j in combinations(range(n), 2):\n",
    "            x1, y1 = points[i]\n",
    "            x2, y2 = points[j]\n",
    "            d = abs(x1 - x2) + abs(y1 - y2)\n",
    "            heapq.heappush(hq, (d, i, j))\n",
    "        # 并查集部分(用来判断是否已经连接)\n",
    "        dic = {}\n",
    "        def find(x):\n",
    "            if x != dic.setdefault(x, x):\n",
    "                dic[x] = find(dic[x])\n",
    "            return dic[x]\n",
    "        ret = 0\n",
    "        while hq:\n",
    "            d, i, j = heapq.heappop(hq)\n",
    "            if find(i) == find(j):\n",
    "                continue\n",
    "            dic[find(i)] = find(j)\n",
    "            ret += d\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        from queue import PriorityQueue\n",
    "        cal = lambda p1, p2: abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])  # 计算曼哈顿距离的函数\n",
    "\n",
    "        pq = PriorityQueue()  # 来，复习一下优先队列的API | PS:要是卡常，就换成\"配对堆\"\n",
    "        visit = set(range(len(points)))  # 待访问的节点集\n",
    "        res = 0\n",
    "\n",
    "        pq.put((0, 0))  # (distance, point_id)  # Prim算法从任何一个节点出发都是一样的，这里从0点开始\n",
    "        while visit:  # 当没有访问完所有节点 | 其它语言的coder请把这行理解成 => while(visit.length() > 0){...}\n",
    "            dis, now = pq.get()  # 获取优先队列中最小的项 => (到扩展集中某最近点的距离，某最近点的序号)\n",
    "            if now not in visit:  # 已访问过的直接跳过\n",
    "                continue\n",
    "            visit.remove(now)  # 随手剪枝，移除出待访问的节点集\n",
    "            res += dis\n",
    "            for i in visit:  # 构建扩展集，就是把当前点对所有未访问点的距离都求一遍\n",
    "                # 以距离为cost丢进优先队列排序就好，想不清明白其它题解费劲构建边结构干啥...\n",
    "                pq.put((cal(points[now], points[i]), i))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        N=len(points)\n",
    "        h=[]\n",
    "        p=set(range(N))\n",
    "        heapq.heappush(h,[0,0])\n",
    "        vis=[False]*N\n",
    "        ans=0\n",
    "        while h and not all(vis):\n",
    "            dis,index=heapq.heappop(h)\n",
    "            if index not in p:continue\n",
    "            xi,yi=points[index]\n",
    "            p.remove(index)\n",
    "            ans+=dis\n",
    "            for i in p:\n",
    "                if vis[i]:continue\n",
    "                xj,yj=points[i]\n",
    "                dis=abs(xi-xj)+abs(yi-yj)\n",
    "                heapq.heappush(h,[dis,i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        #第一步建边\n",
    "        n = len(points)\n",
    "        graph = defaultdict(list)\n",
    "        # 计算两个点之间的曼哈顿距离\n",
    "        def getDis(x,y):\n",
    "            (x1,y1),(x2,y2) = points[x],points[y]\n",
    "            return abs(x1-x2)+abs(y2-y1)\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if i == j:\n",
    "        #             continue\n",
    "        #         (x1,y1),(x2,y2) = points[i],points[j]\n",
    "        #         dis = getDis(x1,y1,x2,y2)\n",
    "        #         graph[i].append([j,dis])\n",
    "        #         graph[j].append([i,dis])\n",
    "        ans = 0\n",
    "        stack = []\n",
    "        # 以点0位开始点搜寻\n",
    "        start = 0\n",
    "        for i in range(1,n):\n",
    "            heappush(stack,[getDis(start,i),i])\n",
    "        record = set(range(n))\n",
    "        record.remove(start)\n",
    "        while stack:\n",
    "            v,cur = heappop(stack)\n",
    "            if cur not in record:\n",
    "                continue\n",
    "            record.remove(cur)\n",
    "            ans += v\n",
    "            for new in record:\n",
    "                heappush(stack,[getDis(cur,new),new])\n",
    "        # print(record)\n",
    "        return ans\n",
    "         \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        #### prim\n",
    "        n = len(points)\n",
    "        cost = 0\n",
    "        import heapq\n",
    "        q = []\n",
    "        unvisited = set([i for i in range(1, n)])\n",
    "        for i in range(1, n):\n",
    "            heapq.heappush(q, [abs(points[0][0] - points[i][0]) + abs(points[0][1] - points[i][1]), i])\n",
    "        while len(unvisited):\n",
    "            dis, y = heapq.heappop(q)\n",
    "            if y in unvisited:\n",
    "               cost += dis\n",
    "               unvisited.remove(y)\n",
    "               for i in unvisited:\n",
    "                   heapq.heappush(q, [abs(points[y][0] - points[i][0]) + abs(points[y][1] - points[i][1]), i]) \n",
    "\n",
    "\n",
    "        return cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        min_heap = [(0, 0)] # (cost, vertex)\n",
    "        res = 0\n",
    "        visited = set()\n",
    "\n",
    "        while len(visited) < len(points):\n",
    "            cost, i = heappop(min_heap)\n",
    "            if i in visited: continue\n",
    "            visited.add(i)\n",
    "            res += cost\n",
    "\n",
    "            x1, y1 = points[i]\n",
    "            for nei in range(len(points)):\n",
    "                if nei not in visited:\n",
    "                    x2, y2 = points[nei]\n",
    "                    heappush(min_heap, (abs(x1-x2)+abs(y1-y2), nei))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        dist = lambda x,y: abs(points[x][0]-points[y][0])+abs(points[x][1]-points[y][1])\n",
    "        if not points:\n",
    "            return 0\n",
    "        size = len(points)\n",
    "        pq = PriorityQueue()\n",
    "        visited = [False] * size\n",
    "        result = 0\n",
    "        count = size - 1\n",
    "        for j in range(size):\n",
    "            pq.put((dist(0,j), 0, j))\n",
    "        visited[0] = True\n",
    "\n",
    "        while pq and count > 0:\n",
    "            e = pq.get()\n",
    "            pointX = e[1]\n",
    "            pointY = e[2]\n",
    "            cost = e[0]\n",
    "            if not visited[pointY]:\n",
    "                result += cost\n",
    "                visited[pointY] = True\n",
    "                for j in range(size):\n",
    "                    if not visited[j]:\n",
    "                        pq.put((dist(pointY, j), pointY, j))\n",
    "                count -= 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        # 连通分量数量\n",
    "        self.count = n\n",
    "        # 连通分量大小\n",
    "        self.size = [1]*n\n",
    "        # 各点的父节点\n",
    "        self.parent = [i for i in range(n)]\n",
    "\n",
    "    def findset(self, x) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def unite(self, x: int, y: int) -> None:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        # 让大的吞并小的\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        # 以x为根的联通分量变大了\n",
    "        self.size[x] += self.size[y]\n",
    "        # 联通分量数 减少\n",
    "        self.count -= 1\n",
    "\n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        return self.findset(x) == self.findset(y)\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        edges = []\n",
    "        heapq.heapify(edges)\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1, len(points)):\n",
    "                distance = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])\n",
    "                heapq.heappush(edges, (distance, i, j))\n",
    "        \n",
    "        weightSum = 0\n",
    "        uf = UF(len(points))\n",
    "        while uf.count > 1:\n",
    "            distance, i, j = edges[0]\n",
    "            heapq.heappop(edges)\n",
    "            if uf.connected(i, j):\n",
    "                continue\n",
    "            weightSum += distance\n",
    "            uf.unite(i, j)\n",
    "\n",
    "        return weightSum\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n =len(points)\n",
    "        g = collections.defaultdict(dict)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i,n):\n",
    "                g[i][j]=g[j][i] = abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])\n",
    "        vist = [0]*n\n",
    "        dist = [float('inf')]*n\n",
    "        q = [[0,0]]\n",
    "        count = 0\n",
    "        res = 0\n",
    "        while q:\n",
    "            d,node = heapq.heappop(q)\n",
    "            if vist[node]:continue \n",
    "            vist[node]=1\n",
    "            res+=d\n",
    "            count+=1\n",
    "            if count == n:\n",
    "                return res\n",
    "            for nex,nexd in g[node].items():\n",
    "                if dist[nex]>nexd:\n",
    "                    dist[nex]=nexd \n",
    "                    heapq.heappush(q,[nexd,nex])\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "\n",
    "        def dist(i, j):\n",
    "            x1, y1 = points[i]\n",
    "            x2, y2 = points[j]\n",
    "            return abs(x1-x2)+abs(y1-y2)\n",
    "\n",
    "        group = {0} # points中index0的点\n",
    "        cost = 0\n",
    "        heap = [[dist(0, i), i] for i in range(1, len(points))] # 距离, 后续节点\n",
    "        heapq.heapify(heap)\n",
    "        while len(group) < len(points):\n",
    "            d, node = heapq.heappop(heap)\n",
    "            if node in group: # 新点已在tree中, 添加会构成环\n",
    "                continue\n",
    "            cost += d\n",
    "            group.add(node)\n",
    "            # 把和node相连的新增可能edge添加到heap中\n",
    "            for nei in range(len(points)):\n",
    "                if nei not in group:\n",
    "                    heapq.heappush(heap, [dist(node, nei), nei])\n",
    "        return cost\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        '''\n",
    "                           *\n",
    "                         /\n",
    "                        /\n",
    "                       * --- * \n",
    "                     /         \\\n",
    "                    *            *\n",
    "        '''\n",
    "        \n",
    "        n = len(points)\n",
    "        dst = []\n",
    "\n",
    "        for i in range(n):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i+1, n):\n",
    "                x2, y2 = points[j]\n",
    "                dst.append((i, j, abs(x1-x2) + abs(y1-y2)))\n",
    "                \n",
    "        dst.sort(key = lambda x: x[2])\n",
    "        parent = [x for x in range(n)]\n",
    "\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        \n",
    "        def union(a, b):\n",
    "            pa, pb = find(a), find(b)\n",
    "            if pa != pb:\n",
    "                parent[pa] = pb\n",
    "                return False\n",
    "            return True\n",
    "        \n",
    "        edges = 0\n",
    "        cost = 0\n",
    "\n",
    "        for a, b, d in dst:\n",
    "            pa, pb = find(a), find(b)\n",
    "            if not union(pa, pb):\n",
    "                edges +=1\n",
    "                cost += d\n",
    "            if edges == n-1: \n",
    "                break\n",
    "        return cost\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.count = n\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1]*n\n",
    "\n",
    "    def union(self, p, q):\n",
    "        rootP = self.find(p)\n",
    "        rootQ = self.find(q)\n",
    "        if rootP == rootQ:\n",
    "            return False\n",
    "        \n",
    "        if self.size[rootP] > self.size[rootQ]:\n",
    "            self.parent[rootQ] = rootP\n",
    "            self.size[rootP] += self.size[rootQ]\n",
    "        else:\n",
    "            self.parent[rootP] = rootQ\n",
    "            self.size[rootQ] += self.size[rootP]\n",
    "        self.count -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self,p, q):\n",
    "        rootP = self.find(p)\n",
    "        rootQ = self.find(q)\n",
    "        return rootP == rootQ\n",
    "    \n",
    "    def find(self, x):\n",
    "        while self.parent[x]!=x:\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "    \n",
    "    def check(self):\n",
    "        return count == 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        edges = []\n",
    "        n = len(points)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                dis = abs(points[i][0]-points[j][0]) + abs(points[i][1] - points[j][1])\n",
    "                edges.append((i, j , dis))\n",
    "        edges.sort(key = lambda x: x[2])\n",
    "        \n",
    "        uf = UF(n)\n",
    "        mst = 0\n",
    "        for edge in edges:\n",
    "            u,v,weight = edge\n",
    "            if uf.union(u,v):\n",
    "                mst += weight\n",
    "            if uf.check():\n",
    "                break\n",
    "        return mst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find(self,parent,i):\n",
    "        if parent[i]==i:\n",
    "            return i\n",
    "        return self.find(parent,parent[i])\n",
    "\n",
    "    def union(self,parent,rank,x,y):\n",
    "        root_x=self.find(parent,x)\n",
    "        root_y=self.find(parent,y)\n",
    "    \n",
    "        if rank[root_x] < rank[root_y]:\n",
    "            parent[root_x] = root_y\n",
    "        elif rank[root_x] > rank[root_y]:\n",
    "            parent[root_y] = root_x\n",
    "        else:\n",
    "            parent[root_x] = root_y\n",
    "            rank[root_y] += 1\n",
    "\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        self.graph=[]\n",
    "        #n=len(points)\n",
    "        for i,p in enumerate(points):\n",
    "            for j in range(i+1,len(points)):\n",
    "                self.graph.append((i,j,abs(p[0]-points[j][0])+abs(p[1]-points[j][1])))\n",
    "\n",
    "        #print(self.graph)\n",
    "        result = []\n",
    "        self.graph = sorted(self.graph, key=lambda item: item[2])\n",
    "        parent = {}\n",
    "        rank = {}\n",
    "\n",
    "        for edge in self.graph:\n",
    "            u, v, w = edge\n",
    "            if u not in parent:\n",
    "                parent[u] = u\n",
    "                rank[u] = 0\n",
    "            if v not in parent:\n",
    "                parent[v] = v\n",
    "                rank[v] = 0\n",
    "\n",
    "            root_u = self.find(parent, u)\n",
    "            root_v = self.find(parent, v)\n",
    "\n",
    "            if root_u != root_v:\n",
    "                result.append((u, v, w))\n",
    "                self.union(parent, rank, root_u, root_v)\n",
    "\n",
    "        \n",
    "   \n",
    "        return sum(r[-1] for r in result)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(points)  # 图的顶点数\n",
    "        visited = set()  # 记录顶点是否已经加入生成树\n",
    "        min_heap = [(0, tuple(points[0]))]  # 优先队列，用于选择最小权值的边\n",
    "        total_cost = 0  # 记录生成树的总权值\n",
    "\n",
    "        while min_heap:\n",
    "            cost, node = heapq.heappop(min_heap)\n",
    "            if node in visited:\n",
    "                continue\n",
    "            visited.add(node)\n",
    "            total_cost += cost\n",
    "\n",
    "            for a, b in points:\n",
    "                if (a, b) not in visited:\n",
    "                    heapq.heappush(min_heap, (abs(node[0] - a) + abs(node[1] - b), (a, b)))\n",
    "\n",
    "        return total_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "\n",
    "        def dist(x1, y1, x2, y2):\n",
    "            return abs(x1 - x2) + abs(y1 - y2) \n",
    "\n",
    "        n = len(points)\n",
    "        connections = []\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                connections.append([i, j, dist(points[i][0], points[i][1], points[j][0], points[j][1])])\n",
    "\n",
    "        connections.sort(key = lambda x: x[2])\n",
    "        ans = 0\n",
    "        p = [i for i in range(n)]\n",
    "\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        \n",
    "        cnt = 1\n",
    "\n",
    "        for x, y, cost in connections:\n",
    "            if find(x) == find(y):\n",
    "                continue\n",
    "            ans += cost\n",
    "            cnt += 1\n",
    "            if cnt == n:\n",
    "                break\n",
    "            p[find(x)] = find(y)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "\n",
    "        def dist(x1, y1, x2, y2):\n",
    "            return abs(x1 - x2) + abs(y1 - y2) \n",
    "\n",
    "        n = len(points)\n",
    "        connections = []\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                connections.append([i, j, dist(points[i][0], points[i][1], points[j][0], points[j][1])])\n",
    "\n",
    "        connections.sort(key = lambda x: x[2])\n",
    "        ans = 0\n",
    "        p = [i for i in range(n)]\n",
    "\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        \n",
    "        cnt = 1\n",
    "\n",
    "        for x, y, cost in connections:\n",
    "            if find(x) == find(y):\n",
    "                continue\n",
    "            ans += cost\n",
    "            cnt += 1\n",
    "            if cnt == n:\n",
    "                break\n",
    "            p[find(x)] = find(y)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "    \n",
    "    def union(self, i, j):\n",
    "        root_i = self.find_parent(i)\n",
    "        root_j = self.find_parent(j)\n",
    "\n",
    "        if root_i ==root_j:\n",
    "            return\n",
    "        self.parent[root_i] = self.parent[root_j]\n",
    "        self.count -= 1\n",
    "        return\n",
    "    \n",
    "    def find_parent(self, i):\n",
    "        if self.parent[i]!=i:\n",
    "            self.parent[i] = self.find_parent(self.parent[i])\n",
    "        return self.parent[i]\n",
    "        # while self.parent[i]!=i:\n",
    "        #     self.parent[i] = self.parent[self.parent[i]]\n",
    "        #     i = self.parent[i]\n",
    "        # return i\n",
    "\n",
    "\n",
    "    \n",
    "    def connected(self, i, j):\n",
    "        return self.find_parent(i)==self.find_parent(j)\n",
    "    \n",
    "    def get_count(self):\n",
    "        return self.count\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        # 构造图\n",
    "        n = len(points)\n",
    "        uf = UF(n)\n",
    "        graph = []\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                dist = abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1])\n",
    "                edge = [dist, i, j]\n",
    "                graph.append(edge)\n",
    "        # Kruskal算法\n",
    "        mindist = 0\n",
    "        graph = sorted(graph)\n",
    "        for dist, i, j in graph:\n",
    "            if uf.connected(i,j):\n",
    "                continue\n",
    "            mindist += dist\n",
    "            uf.union(i,j)\n",
    "        return mindist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import defaultdict\n",
    "# from heapq import *\n",
    "# class Solution:\n",
    "#     def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "#         def distance(i,j):\n",
    "#             return abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])\n",
    "#         #最小生成树，prim算法，\n",
    "#         #构图，相当于完全图，每两个点之间都有路径\n",
    "#         graph=defaultdict(list)\n",
    "#         for i in range(len(points)):\n",
    "#             for j in range(len(points)):\n",
    "#                 if j==i:continue\n",
    "#                 graph[i].append([j,distance(i,j)])\n",
    "#                 graph[j].append([i,distance(i,j)])\n",
    "#         tree=set()\n",
    "#         all_cost=0\n",
    "#         que=[(0,0)]#制定一个起点，(weight,i)\n",
    "#         while que:\n",
    "#             for _ in range(len(que)):\n",
    "#                 w,i=heappop(que)\n",
    "#                 if i not in tree:\n",
    "#                     tree.add(i)\n",
    "#                     all_cost+=w \n",
    "#                     if len(tree)==len(points):return all_cost\n",
    "#                     for j,w in graph[i]:\n",
    "#                         heappush(que,(w,j))\n",
    "#         if len(tree)!=len(points):return -1\n",
    "#         else:return all_cost\n",
    "#         # return all_cost\n",
    "\n",
    "from collections import defaultdict\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.parent=[i for i in range(n)]\n",
    "        self.size=[1]*n\n",
    "        #self.parts=0 #总共有多少个联通块\n",
    "        self.parts=n #总共有多少个联通块\n",
    "    def find(self,x):\n",
    "        if self.parent[x]!=x:#还没有找到根节点\n",
    "            self.parent[x]=self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def union(self,x,y):\n",
    "        father1=self.find(x)\n",
    "        father2=self.find(y)\n",
    "        if father1==father2:return False\n",
    "        if self.size[father1]>self.size[father2]:\n",
    "            self.parent[father2]=father1\n",
    "            self.size[father1]+=self.size[father2]\n",
    "            self.size[father2]=0#非根节点的秩置为0，是否需要这一步呢\n",
    "        else:\n",
    "            self.parent[father1]=father2\n",
    "            self.size[father2]+=self.size[father1]\n",
    "            self.size[father1]=0#非根节点的秩置为0，是否需要这一步呢\n",
    "        self.parts-=1\n",
    "        return self.parts\n",
    "    def is_connect(self,x,y):\n",
    "        return self.find(x)==self.find(y)\n",
    "    def get_root_part(self):#获取每个根节点对应的组\n",
    "        parts=defaultdict(list)#注意不是self.parts\n",
    "        n=len(self.parent)\n",
    "        for i in range(n):\n",
    "            parts[self.find(i)].append(i)\n",
    "        return parts\n",
    "    def get_root_size(self):\n",
    "        size=defaultdict(int)\n",
    "        n=len(self.parent)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)]=self.size[self.find(i)]\n",
    "        return size\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n=len(points)\n",
    "        connections=[]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                connections.append([i,j,abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])])\n",
    "        uf=UnionFind(n)\n",
    "        connections.sort(key=lambda x:x[2])\n",
    "        all_cost=0\n",
    "        for i,j,cost in connections:\n",
    "            if not uf.is_connect(i,j):\n",
    "                uf.union(i,j)\n",
    "                all_cost+=cost\n",
    "        return all_cost\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        k = (n * (n-1)) // 2\n",
    "        edges = [0] * k \n",
    "        index = 0\n",
    "        for i in range(n):\n",
    "            point1 = points[i]\n",
    "            for j in range(i+1, n):\n",
    "                point2 = points[j]\n",
    "                dis = abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])\n",
    "                edges[index] = [i, j, dis]\n",
    "                index += 1\n",
    "        \n",
    "        edges = sorted(edges, key = lambda x: x[2])\n",
    "        fa = [0] * n\n",
    "        for i in range(n):\n",
    "            fa[i] = i\n",
    "        \n",
    "        def find(x):\n",
    "            if x == fa[x]:\n",
    "                return x\n",
    "            else:\n",
    "                fa[x] = find(fa[x])\n",
    "                return fa[x]\n",
    "        def union(x, y):\n",
    "            fa[find(x)] = find(y)\n",
    "        \n",
    "        ans = 0\n",
    "        for edge in edges:\n",
    "            i, j, dis = edge[0], edge[1], edge[2]\n",
    "            if find(i) != find(j):\n",
    "                union(i, j)\n",
    "                ans += dis\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        edges = []\n",
    "        for i in range(0, len(points)):\n",
    "            for j in range(i+1, len(points)):\n",
    "                edges.append([i, j, abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])])\n",
    "        edges = sorted(edges, key=lambda x:x[2])\n",
    "        fa = [i for i in range(len(points))]\n",
    "        def find(node):\n",
    "            if fa[node] == node:\n",
    "                return fa[node]\n",
    "            else:\n",
    "                fa[node] = find(fa[node])\n",
    "                return fa[node]\n",
    "        res = 0\n",
    "        for u, v, dis in edges:\n",
    "            if find(u) == find(v):\n",
    "                continue\n",
    "            else:\n",
    "                fa[find(u)] = find(v)\n",
    "                res += dis\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        ps = list(range(len(points)))\n",
    "        def find(p):\n",
    "            if ps[p]!=p:\n",
    "                return find(ps[p])\n",
    "            return ps[p]\n",
    "            \n",
    "        tmp = []\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1,len(points)):\n",
    "                d = abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])\n",
    "                tmp.append([i,j,d])\n",
    "        tmp = sorted(tmp,key=lambda x:x[-1])\n",
    "        l = 0\n",
    "        for line in tmp:\n",
    "            p1,p2,w = line\n",
    "            if find(p1)==find(p2):\n",
    "                continue\n",
    "            ps[find(p1)]=find(p2)\n",
    "\n",
    "            l+=w\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    \"\"\"\r\n",
    "        Minimum Spanning Tree (MST)\r\n",
    "        1. Kruskal's algorithm\r\n",
    "    \"\"\"\r\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\r\n",
    "        graph = []\r\n",
    "        n = len(points) # number of points\r\n",
    "        for i, j in combinations(range(n), 2):\r\n",
    "            x1, y1 = points[i]\r\n",
    "            x2, y2 = points[j]\r\n",
    "            graph.append( [(i, j), abs(x1-x2)+abs(y1-y2)] )\r\n",
    "\r\n",
    "        # Disjoint Set & Union\r\n",
    "        parent = [i for i in range(n)]\r\n",
    "        def find(x):\r\n",
    "            if x != parent[x]:\r\n",
    "                parent[x] = find(parent[x])\r\n",
    "            return parent[x]\r\n",
    "\r\n",
    "        # Kruskal's algorithm\r\n",
    "        graph.sort(key=lambda x:x[1]) # sort by distance\r\n",
    "        edge = 0\r\n",
    "        cost = 0\r\n",
    "        for (i, j), d in graph:\r\n",
    "            a, b = find(i), find(j)\r\n",
    "            if a != b: # if a, b not in the same set\r\n",
    "                parent[b] = a\r\n",
    "                edge += 1\r\n",
    "                cost += d\r\n",
    "            if edge == n-1: # if all points are connected\r\n",
    "                break\r\n",
    "        return cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        dis = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        edges = []\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                p1 = points[i]\n",
    "                p2 = points[j]\n",
    "                distance = abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])\n",
    "                dis[i][j] = dis[j][i] = distance\n",
    "                edges.append([i, j, distance])\n",
    "        edges.sort(key=lambda e: e[2])\n",
    "\n",
    "        uf_p = [i for i in range(n)]\n",
    "\n",
    "        def find(x: int) -> int:\n",
    "            if uf_p[x] == x:\n",
    "                return x\n",
    "            uf_p[x] = find(uf_p[x])\n",
    "            return uf_p[x]\n",
    "\n",
    "        def union(x: int, y: int):\n",
    "            uf_p[find(x)] = find(y)\n",
    "\n",
    "        fee = 0\n",
    "        for e in edges:\n",
    "            if find(e[0]) != find(e[1]):\n",
    "                fee += e[2]\n",
    "                union(e[0], e[1])\n",
    "        return fee"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#prim\n",
    "# class Solution:\n",
    "#     def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "#         n = len(points)\n",
    "#         g = [[0] * n for _ in range(n)]\n",
    "#         dist = [inf] * n\n",
    "#         vis = [False] * n\n",
    "#         #算出i，j距离\n",
    "#         for i, (x1, y1) in enumerate(points):\n",
    "#             for j in range(i + 1, n):\n",
    "#                 x2, y2 = points[j]\n",
    "#                 t = abs(x1 - x2) + abs(y1 - y2)\n",
    "#                 g[i][j] = g[j][i] = t\n",
    "#         dist[0] = 0\n",
    "#         ans = 0\n",
    "#         for _ in range(n):\n",
    "#             #要把n个加入选择\n",
    "#             i = -1\n",
    "#             #在未被选择的里面选一个最小的\n",
    "#             for j in range(n):\n",
    "#                 if not vis[j] and (i == -1 or dist[j] < dist[i]):\n",
    "#                     i = j\n",
    "#             vis[i] = True\n",
    "#             ans += dist[i]\n",
    "#             #更新未被选择的点离已完成的图里\n",
    "#             for j in range(n):\n",
    "#                 if not vis[j]:\n",
    "#                     dist[j] = min(dist[j], g[i][j])\n",
    "#         return ans\n",
    "# 堆优化\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        g = defaultdict(list)\n",
    "        dist = [inf] * n\n",
    "        #算出i，j距离\n",
    "        for i, (x1, y1) in enumerate(points):\n",
    "            for j in range(i + 1, n):\n",
    "                x2, y2 = points[j]\n",
    "                t = abs(x1 - x2) + abs(y1 - y2)\n",
    "                g[i].append((j,t))\n",
    "                g[j].append((i,t))\n",
    "        dist[0] = 0\n",
    "        ans = 0\n",
    "        vis = [False]*n\n",
    "        q=[(0,0)]#disttomintree,cur \n",
    "        while q and not all(vis):\n",
    "            #要把n个加入选择\n",
    "            distance, cur = heappop(q)\n",
    "            #在未被选择的里面选一个最小的\n",
    "            if vis[cur]:\n",
    "                continue\n",
    "            vis[cur] = True\n",
    "            ans += distance\n",
    "         \n",
    "            for point,weight in g[cur]:\n",
    "                if dist[point] > weight:\n",
    "                    dist[point] = weight\n",
    "                    heappush(q,(dist[point],point))\n",
    "\n",
    "            #更新未被选择的点离已完成的图里\n",
    "        \n",
    "        return ans\n",
    "\n",
    "#Kruskal，按距离排序，选n个，用并查集\n",
    "# class Solution:\n",
    "#     def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "\n",
    "#         def find(x):\n",
    "#             if p[x] != x:\n",
    "#                 p[x] = find(p[x])\n",
    "#             return p[x]\n",
    "\n",
    "#         n = len(points)\n",
    "#         g = []\n",
    "#         ans = 0\n",
    "#         #set parent of each element to be themself\n",
    "#         p = list(range(n))\n",
    "#         #算出i，j距离\n",
    "#         for i, (x1, y1) in enumerate(points):\n",
    "#             for j in range(i + 1, n):\n",
    "#                 x2, y2 = points[j]\n",
    "#                 t = abs(x1 - x2) + abs(y1 - y2)\n",
    "#                 g.append((t,i,j))\n",
    "#         g.sort(key=lambda x:x[0])\n",
    "#         for cost,i,j in g:\n",
    "#             if find(i) == find(j):\n",
    "#                 continue\n",
    "#             p[find(i)] = find(j)\n",
    "#             ans += cost\n",
    "#             n -=1\n",
    "#             if n == 1:\n",
    "#                 break\n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                dis = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])\n",
    "                graph[i].append((dis, i, j))\n",
    "                graph[j].append((dis, j, i))\n",
    "        p = Prim(graph)\n",
    "        return p.weightsum\n",
    "\n",
    "       \n",
    "\n",
    "class Prim:\n",
    "    def __init__(self, graph):\n",
    "        self.graph = graph\n",
    "        self.pq = []\n",
    "        self.inMST = [False] *  len(graph)\n",
    "        self.inMST[0] = True\n",
    "        self.weightsum = 0\n",
    "        self.cut(0)\n",
    "\n",
    "        while self.pq:\n",
    "            edge = heapq.heappop(self.pq)\n",
    "            if self.inMST[edge[2]]: # 节点 to 已经在最小生成树中，跳过。否则这条边会产生环\n",
    "                continue\n",
    "            self.weightsum += edge[0]\n",
    "            self.inMST[edge[2]] = True\n",
    "            self.cut(edge[2])\n",
    "    \n",
    "    def cut(self, node):\n",
    "        for edge in self.graph[node]:\n",
    "            if not self.inMST[edge[2]]:\n",
    "                heapq.heappush(self.pq, edge)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Union:\n",
    "    def __init__(self, size):\n",
    "        self.rank = [1 for _ in range(size)]\n",
    "        self.root = [i for i in range(size)]\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.root[x] == x:\n",
    "            return self.root[x]\n",
    "        \n",
    "        self.root[x] = self.find(self.root[x])\n",
    "        return self.root[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "\n",
    "        if self.rank[x] > self.rank[y]:\n",
    "            self.root[rootY] = x\n",
    "        elif self.rank[y] > self.rank[x]:\n",
    "            self.root[rootX] = y\n",
    "        else:\n",
    "            self.root[rootY] = x\n",
    "            self.rank[rootX] += 1\n",
    "    \n",
    "    def isConnected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        if len(points) == 0:\n",
    "            return 0\n",
    "\n",
    "        import heapq\n",
    "        heap = []\n",
    "\n",
    "        n = len(points)\n",
    "\n",
    "        union_helper = Union(n)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i + 1, len(points)):\n",
    "                dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])\n",
    "                heapq.heappush(heap, (dist, [i, j]))\n",
    "        \n",
    "        aim = n - 1\n",
    "        while len(heap) > 0 and aim > 0:\n",
    "            cur_edge = heapq.heappop(heap)\n",
    "            if not union_helper.isConnected(cur_edge[1][0], cur_edge[1][1]):\n",
    "                union_helper.union(cur_edge[1][0], cur_edge[1][1])\n",
    "                ans += cur_edge[0]\n",
    "                aim -= 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class edge:\n",
    "    def __init__(self, pos1, pos2, value: int):\n",
    "        self.pos1 = pos1\n",
    "        self.pos2 = pos2\n",
    "        self.value = value\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        pointlist = []\n",
    "        edgelist = []\n",
    "        conndict = {}\n",
    "        for point in points:\n",
    "            pointlist.append((point[0], point[1]))\n",
    "        pointnum = len(pointlist)\n",
    "        for i in range(pointnum):\n",
    "            for j in range(i+1, pointnum):\n",
    "                dis = abs(pointlist[i][0] - pointlist[j][0]) + abs(pointlist[i][1] - pointlist[j][1])\n",
    "                edgei = edge(pointlist[i], pointlist[j], dis)\n",
    "                edgelist.append(edgei)\n",
    "        edgelist = sorted(edgelist, key=lambda x:x.value)\n",
    "        ansres = 0\n",
    "        for edgei in edgelist:\n",
    "            if conndict.get(edgei.pos1) == None:\n",
    "                conndict[edgei.pos1] = edgei.pos1\n",
    "            if conndict.get(edgei.pos2) == None:\n",
    "                conndict[edgei.pos2] = edgei.pos2\n",
    "            fapos1 = edgei.pos1\n",
    "            while conndict.get(fapos1) != None and conndict.get(fapos1) != fapos1:\n",
    "                fapos1 = conndict.get(fapos1)\n",
    "            nowpos = edgei.pos1\n",
    "            while conndict.get(nowpos) != fapos1:\n",
    "                nxtpos = conndict.get(nowpos)\n",
    "                conndict[nowpos] = fapos1\n",
    "                nowpos = nxtpos\n",
    "            fapos2 = edgei.pos2\n",
    "            while conndict.get(fapos2) != None and conndict.get(fapos2) != fapos2:\n",
    "                fapos2 = conndict.get(fapos2)\n",
    "            nowpos = edgei.pos2\n",
    "            while conndict.get(nowpos) != fapos2:\n",
    "                nxtpos = conndict.get(nowpos)\n",
    "                conndict[nowpos] = fapos2\n",
    "                nowpos = nxtpos\n",
    "            if fapos1 != fapos2:\n",
    "                conndict[fapos1] = fapos2\n",
    "                ansres += edgei.value\n",
    "        return ansres\n",
    "\n",
    "            \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, start, end, cost):\n",
    "        self.start, self.end, self.cost = start, end, cost\n",
    "\n",
    "    def __lt__(self, nx):\n",
    "        return self.cost < nx.cost\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        dist = lambda p, q: abs(p[0]-q[0]) + abs(p[1]-q[1])\n",
    "        n = len(points)\n",
    "        distances = []\n",
    "        visit = [False] * n\n",
    "        visit[0] = True\n",
    "        \n",
    "        for j in range(n):\n",
    "            if not visit[j]:\n",
    "                d = dist(points[0], points[j])\n",
    "                heapq.heappush(distances, Node(0, j, d))\n",
    "        \n",
    "        edge_cnt = 0\n",
    "        res = 0\n",
    "        while edge_cnt < n - 1:\n",
    "            cur = heapq.heappop(distances)\n",
    "            _, j, d = cur.start, cur.end, cur.cost\n",
    "            if visit[j]:\n",
    "                continue\n",
    "            \n",
    "            visit[j] = True\n",
    "            res += d\n",
    "            edge_cnt += 1\n",
    "            \n",
    "            for k in range(n):\n",
    "                if not visit[k]:\n",
    "                    d = dist(points[j], points[k])\n",
    "                    heapq.heappush(distances, Node(j, k, d))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        calc = lambda p1, p2: abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])\n",
    "        n = len(points)\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                dist = calc(points[i], points[j])\n",
    "                dic[i].append((dist, j))\n",
    "                dic[j].append((dist, i))\n",
    "\n",
    "        visited = [1] + [0]*(n-1)\n",
    "        heap = dic[0]\n",
    "        heapify(heap)\n",
    "        cnt = 1\n",
    "        res = 0\n",
    "        while heap:\n",
    "            dist, idx = heappop(heap)\n",
    "            if not visited[idx]:\n",
    "                visited[idx] = 1\n",
    "                cnt += 1\n",
    "                res += dist\n",
    "                for v in dic[idx]:\n",
    "                    heappush(heap, v)\n",
    "            if cnt >= n:\n",
    "                break\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        n = len(points)\n",
    "        dis = []\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                val = abs((points[i][0] - points[j][0])) + abs((points[i][1] - points[j][1]))\n",
    "                g[i].append([j, val])\n",
    "                g[j].append([i, val])\n",
    "        s = set()\n",
    "        s.add(0)\n",
    "        ans = 0\n",
    "        t = 0\n",
    "        vis = [False] * n\n",
    "        vis[0] = True\n",
    "        lowcast = [inf] * n\n",
    "        lowcast[0] = 0\n",
    "        for f in g[0]:\n",
    "            i, val = f\n",
    "            lowcast[i] = val\n",
    "        t = 0\n",
    "        while len(s) != n:\n",
    "            #print(lowcast)\n",
    "            mn = inf\n",
    "            id = 0\n",
    "            for i in range(n):\n",
    "                if not vis[i] and lowcast[i] < mn:\n",
    "                    id = i\n",
    "                    mn = lowcast[i]\n",
    "            vis[id] = True \n",
    "            s.add(id)\n",
    "            ans += mn\n",
    "            print(id, mn)\n",
    "            for f in g[id]:\n",
    "                i, val = f\n",
    "                if not vis[i] and val < lowcast[i]:\n",
    "                    lowcast[i] = val \n",
    "            t += 1\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet(object):\n",
    "    def __init__(self, n):\n",
    "        self.roots = [-1 for i in range(n)]\n",
    "        self.rank = [0 for i in range(n)]\n",
    "        self.count = n\n",
    "        \n",
    "        for i in range(n):\n",
    "            self.roots[i] = i\n",
    "        \n",
    "    def find(self, member):\n",
    "        tmp = []\n",
    "        while member != self.roots[member]:\n",
    "            tmp.append(member)\n",
    "            member = self.roots[member]\n",
    "        for root in tmp:\n",
    "            self.roots[root] = member\n",
    "        return member\n",
    "        \n",
    "    def union(self, p, q):\n",
    "        parentP = self.find(p)\n",
    "        parentQ = self.find(q)\n",
    "        if parentP != parentQ:\n",
    "            if self.rank[parentP] > self.rank[parentQ]:\n",
    "                self.roots[parentQ] = parentP\n",
    "            elif self.rank[parentP] < self.rank[parentQ]:\n",
    "                self.roots[parentP] = parentQ\n",
    "            else:\n",
    "                self.roots[parentQ] = parentP\n",
    "                self.rank[parentP] -= 1\n",
    "            self.count -= 1\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        def get_distance(i, j):\n",
    "            return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])\n",
    "        edges = []\n",
    "        n = len(points)\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i + 1, len(points)):\n",
    "                edges.append((i, j, get_distance(i, j)))\n",
    "        \n",
    "        res = 0\n",
    "        edges.sort(key = lambda x: x[2])\n",
    "        ufs = UnionFindSet(n ** 2)\n",
    "        for src, des, dist in edges:\n",
    "            if ufs.find(src) != ufs.find(des):\n",
    "                ufs.union(src, des)\n",
    "                res += dist\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        if n==1: return 0\n",
    "        edges = []\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                cost = abs(points[i][0] - points[j][0]) + abs(points[i][1]-points[j][1])\n",
    "                edges.append(edge(i,j,cost))\n",
    "        \n",
    "        edges.sort(key = lambda x: x.cost)\n",
    "        res, count = 0, 0\n",
    "        uf = unionFind(n)\n",
    "        for e in edges:\n",
    "            if count == n-1:\n",
    "                break\n",
    "            if uf.isConnected(e.i, e.j):\n",
    "                continue\n",
    "            uf.union(e.i, e.j)\n",
    "            count+=1\n",
    "            res+=e.cost\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "class edge():\n",
    "    def __init__(self, i, j, cost):\n",
    "        self.i = i\n",
    "        self.j = j\n",
    "        self.cost = cost\n",
    "\n",
    "\n",
    "\n",
    "class unionFind():\n",
    "    def __init__(self, n):\n",
    "        self.root = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "    \n",
    "    def find(self, x):\n",
    "        rootX = self.root[x]\n",
    "        if x==rootX:\n",
    "            return x\n",
    "        self.root[x] = self.find(rootX)\n",
    "        return self.root[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX!=rootY:\n",
    "            if self.rank[rootX]<self.rank[rootY]:\n",
    "                self.root[rootX] = rootY\n",
    "            elif self.rank[rootY]< self.rank[rootX]:\n",
    "                self.root[rootY]= rootX\n",
    "            else:\n",
    "                self.root[rootX] = rootY\n",
    "                self.rank[rootY] += 1\n",
    "\n",
    "    def isConnected(self, x, y):\n",
    "        return self.find(x)==self.find(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(len(points))]\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i + 1, len(points)):\n",
    "                weight = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])\n",
    "                graph[i].append([weight, j])\n",
    "                graph[j].append([weight, i])\n",
    "        self.pq = []\n",
    "        heapq.heapify(self.pq)\n",
    "        self.in_mst = set()\n",
    "        self.cut(graph, 0)\n",
    "        self.in_mst.add(0)\n",
    "        mst = 0\n",
    "        while self.pq:\n",
    "            edge = heapq.heappop(self.pq)\n",
    "            dst = edge[1]\n",
    "            weight = edge[0]\n",
    "            if dst in self.in_mst:\n",
    "                continue\n",
    "            mst += weight\n",
    "            self.in_mst.add(dst)\n",
    "            if len(self.in_mst) == len(points):\n",
    "                break\n",
    "            self.cut(graph,dst)\n",
    "        \n",
    "        return mst\n",
    "            \n",
    "\n",
    "\n",
    "    \n",
    "    def cut(self, graph, node):\n",
    "        for edge in graph[node]:\n",
    "            neighbor = edge[1]\n",
    "            if neighbor in self.in_mst:\n",
    "                continue\n",
    "            heapq.heappush(self.pq, edge)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjointSet:\n",
    "    def __init__(self, n):\n",
    "        self.p = [i for i in range(n)]\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.p[x]:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        p_x = self.find(x)\n",
    "        p_y = self.find(y)\n",
    "        if p_x != p_y:\n",
    "            if self.rank[p_x] < self.rank[p_y]:\n",
    "                self.p[p_x] = p_y\n",
    "            elif self.rank[p_x] > self.rank[p_y]:\n",
    "                self.p[p_y] = p_x\n",
    "            else:\n",
    "                self.p[p_x] = p_y\n",
    "                self.rank[p_x] += 1\n",
    "\n",
    "\n",
    "class Kruskal:\n",
    "    def __init__(self, n, E, grid):\n",
    "        self.ds = DisjointSet(n)\n",
    "        self.E = E\n",
    "        self.grid = grid\n",
    "\n",
    "    def build(self):\n",
    "        cost = 0\n",
    "        self.E = sorted(self.E, key=lambda item: item[1])\n",
    "        for (i, j), _ in self.E:\n",
    "            if self.ds.find(i) != self.ds.find(j):\n",
    "                self.ds.union(i, j)\n",
    "                cost += self.grid[i][j]\n",
    "\n",
    "        return cost\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(points)\n",
    "        E = []\n",
    "        grid = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                dis = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])\n",
    "                grid[i][j] = dis\n",
    "                E.append([(i, j), dis])\n",
    "\n",
    "        k = Kruskal(n,E, grid)\n",
    "        return k.build()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        import heapq\n",
    "        n=len(points)\n",
    "        choice=[0]\n",
    "        edges=[]\n",
    "\n",
    "        res=0\n",
    "\n",
    "        def get_dis(a,b):\n",
    "            return abs(a[0]-b[0])+abs(a[1]-b[1])\n",
    "\n",
    "        while len(choice)<n:\n",
    "            for i in range(n):\n",
    "                if points[i]!=points[choice[-1]]:\n",
    "                    heapq.heappush(edges,(get_dis(points[i],points[choice[-1]]),choice[-1],i))\n",
    "            \n",
    "            while 1:\n",
    "                e=heapq.heappop(edges)\n",
    "                if e[-1] not in choice:\n",
    "                    choice.append(e[-1])\n",
    "                    res+=e[0]\n",
    "                    break\n",
    "        \n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # n=len(points)\n",
    "        # parent=list(range(n+1))\n",
    "\n",
    "        # def find(v):\n",
    "        #     if parent[v]!=v:\n",
    "        #         parent[v]=find(parent[v])\n",
    "        #     return parent[v]\n",
    "        \n",
    "        # def union(v1,v2):\n",
    "        #     parent[find(v1)]=parent[find(v2)]\n",
    "        \n",
    "        # def get_dis(a,b):\n",
    "        #     return abs(a[0]-b[0])+abs(a[1]-b[1])\n",
    "        \n",
    "        # edges=[]\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+1,n):\n",
    "        #         edges.append((get_dis(points[i],points[j]),i,j))\n",
    "        \n",
    "        # edges.sort(reverse=True)\n",
    "        \n",
    "        # num=0\n",
    "        # res=0\n",
    "        # while num<n-1:\n",
    "        #     e=edges.pop()\n",
    "        #     if find(e[1])!=find(e[2]):\n",
    "        #         num+=1\n",
    "        #         res+=e[0]\n",
    "        #         union(e[1],e[2])\n",
    "        \n",
    "        # return res\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        \n",
    "        n = len(points)\n",
    "        dist = []\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                dist.append((abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), i, j))\n",
    "        \n",
    "        heapq.heapify(dist)\n",
    "\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        parent = [i for i in range(n)]\n",
    "\n",
    "        def find(index):\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1, index2):\n",
    "            if index1 > index2:\n",
    "                index1, index2 = index2, index1\n",
    "            \n",
    "            parent[find(index2)] = find(index1)\n",
    "\n",
    "        while count < n - 1:\n",
    "            dis, i, j = heapq.heappop(dist)\n",
    "            if find(i) != find(j):\n",
    "                ans += dis\n",
    "                union(i, j)\n",
    "                count += 1\n",
    "            \n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Prim:\n",
    "    def __init__(self, graph: List[List[int]]):\n",
    "        self.graph = graph\n",
    "        self.vertexNum = len(self.graph)\n",
    "        self.visited = [False] * self.vertexNum   # 记录顶点是否被访问\n",
    "        self.minWeights = [float('inf')] * self.vertexNum  # 记录权值最小的边\n",
    "        self.minWeights[0] = 0   # 从任意一个点出发都可以\n",
    "\n",
    "    def weightSum(self) -> int:\n",
    "        res = 0\n",
    "        for i in range(self.vertexNum):\n",
    "            u = self.getMinWeightVertex()\n",
    "            self.visited[u] = True\n",
    "            res += self.minWeights[u]\n",
    "            # 更新未访问顶点的边\n",
    "            for edge in self.graph[u]:\n",
    "                v, weight = edge[1], edge[2]\n",
    "                if not self.visited[v] and weight < self.minWeights[v]:\n",
    "                    self.minWeights[v] = weight\n",
    "        return res\n",
    "\n",
    "    def getMinWeightVertex(self) -> int:\n",
    "        minWeight, minVertex = float('inf'), -1\n",
    "        for i in range(self.vertexNum):\n",
    "            if not self.visited[i] and self.minWeights[i] < minWeight:\n",
    "                minWeight = self.minWeights[i]\n",
    "                minVertex = i\n",
    "        return minVertex\n",
    "\n",
    "class Solution():\n",
    "    def minCostConnectPoints(self,points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        graph = self.buildGraph(n, points)\n",
    "        return Prim(graph).weightSum()\n",
    "\n",
    "\n",
    "    def buildGraph(self,n: int, points: List[List[int]]) -> List[List[int]]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        # 生成所有边及权重\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                xi, yi = points[i]\n",
    "                xj, yj = points[j]\n",
    "                weight = abs(xi - xj) + abs(yi - yj)\n",
    "                # 用 points 中的索引表示坐标点\n",
    "                graph[i].append([i, j, weight])\n",
    "                graph[j].append([j, i, weight])\n",
    "        return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        if n==1: return 0\n",
    "        edges = []\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                cost = abs(points[i][0] - points[j][0]) + abs(points[i][1]-points[j][1])\n",
    "                edges.append(edge(i,j,cost))\n",
    "        \n",
    "        edges.sort(key = lambda x: x.cost)\n",
    "        res, count = 0, 0\n",
    "        uf = unionFind(len(edges)+1)\n",
    "        for e in edges:\n",
    "            if count == n-1:\n",
    "                break\n",
    "            if uf.isConnected(e.i, e.j):\n",
    "                continue\n",
    "            uf.union(e.i, e.j)\n",
    "            count+=1\n",
    "            res+=e.cost\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "class edge():\n",
    "    def __init__(self, i, j, cost):\n",
    "        self.i = i\n",
    "        self.j = j\n",
    "        self.cost = cost\n",
    "\n",
    "\n",
    "\n",
    "class unionFind():\n",
    "    def __init__(self, n):\n",
    "        self.root = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "    \n",
    "    def find(self, x):\n",
    "        rootX = self.root[x]\n",
    "        if x==rootX:\n",
    "            return x\n",
    "        self.root[x] = self.find(rootX)\n",
    "        return self.root[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX!=rootY:\n",
    "            if self.rank[rootX]<self.rank[rootY]:\n",
    "                self.root[rootX] = rootY\n",
    "            elif self.rank[rootY]< self.rank[rootX]:\n",
    "                self.root[rootY]= rootX\n",
    "            else:\n",
    "                self.root[rootX] = rootY\n",
    "                self.rank[rootY] += 1\n",
    "\n",
    "    def isConnected(self, x, y):\n",
    "        return self.find(x)==self.find(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        https://leetcode.cn/problems/all-paths-from-source-to-target/description/\n",
    "\n",
    "        dfs / brute force:\n",
    "            Time:\n",
    "                number of possible paths: 2^V\n",
    "                copy cost: V\n",
    "                -> time: V * 2^V\n",
    "            Space: call stack: V\n",
    "\n",
    "        Tests:\n",
    "        (([[0, 0]],), 0),\n",
    "        (([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]],), 20),\n",
    "        (([[3, 12], [-2, 5], [-4, 1]],), 18),\n",
    "        (([[0, 0], [1, 1], [1, 0], [-1, 1]],), 4),\n",
    "        (([[0, 0], [1, 1], [1, 0], [-1, 1]],), 4),\n",
    "        (([[-1000000, -1000000], [1000000, 1000000]],), 4000000),\n",
    "        \"\"\"\n",
    "\n",
    "        def get_adjacency_list_graph(points):\n",
    "            graph = {}\n",
    "            for i_from_point, from_point in enumerate(points):\n",
    "                from_point_edges = []\n",
    "                for i_to_point, to_point in enumerate(points):\n",
    "                    if i_from_point == i_to_point:\n",
    "                        continue\n",
    "                    weight = abs(from_point[0] - to_point[0]) + abs(\n",
    "                        from_point[1] - to_point[1]\n",
    "                    )\n",
    "                    from_point_edges.append((weight, i_from_point, i_to_point))\n",
    "                graph[i_from_point] = from_point_edges\n",
    "            return graph\n",
    "\n",
    "        import heapq\n",
    "\n",
    "        class Prim:\n",
    "            def __init__(self):\n",
    "                self.mst_cost = 0\n",
    "\n",
    "            def main(self, graph: dict) -> list:\n",
    "                \"\"\"\n",
    "                graph: adjacency list like structure. E.g.\n",
    "                    {\n",
    "                        v1: [(cost12, from (v1), to (v2))],\n",
    "                        v2: [(cost12, from (v2), to (v1))],\n",
    "                    }\n",
    "                \"\"\"\n",
    "                if not graph:\n",
    "                    return []\n",
    "\n",
    "                # Arbitrarily start from the first vertex\n",
    "                [\n",
    "                    starting_vertex,\n",
    "                    *unvisited,\n",
    "                ] = graph.keys()  # `.keys()` is optional\n",
    "                mst_vertices = [starting_vertex]\n",
    "\n",
    "                mst_edges = []\n",
    "                min_heap = graph[starting_vertex]\n",
    "                heapq.heapify(min_heap)\n",
    "\n",
    "                while unvisited:\n",
    "                    (cost, from_v, to_v) = heapq.heappop(min_heap)\n",
    "                    new_mst_vertex = None\n",
    "\n",
    "                    if to_v in unvisited and from_v in mst_vertices:\n",
    "                        new_mst_vertex = to_v\n",
    "                        mst_edges.append((from_v, to_v, cost))\n",
    "\n",
    "                    # elif to_v in mst_vertices and from_v in unvisited:\n",
    "                    #     new_mst_vertex = from_v\n",
    "                    #     mst_edges.append((to_v, from_v, cost))\n",
    "\n",
    "                    if new_mst_vertex is not None:\n",
    "                        unvisited.remove(new_mst_vertex)\n",
    "                        mst_vertices.append(new_mst_vertex)\n",
    "                        self.mst_cost += cost\n",
    "\n",
    "                        for new_edge in graph[new_mst_vertex]:\n",
    "                            heapq.heappush(min_heap, new_edge)\n",
    "\n",
    "                return mst_edges\n",
    "\n",
    "        prim = Prim()\n",
    "        prim.main(get_adjacency_list_graph(points))\n",
    "        return prim.mst_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        graph = {i: [] for i in range(len(points))}\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1, len(points)):\n",
    "                x1, y1 = points[i]\n",
    "                x2, y2 = points[j]\n",
    "                dist = abs(x1 - x2) + abs(y1 - y2)\n",
    "                graph[i].append((dist, j))\n",
    "                graph[j].append((dist, i))\n",
    "\n",
    "        min_heap = [(0, 0)] # (cost, vertex)\n",
    "        res = 0\n",
    "        visited = set()\n",
    "        while len(visited) < len(points):\n",
    "            cost, i = heappop(min_heap)\n",
    "            if i in visited: continue\n",
    "            visited.add(i)\n",
    "            res += cost\n",
    "            for nei_cost, nei in graph[i]:\n",
    "                if nei not in visited:\n",
    "                    heappush(min_heap, (nei_cost, nei))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        def distance(x1, y1, x2, y2):\n",
    "            return abs(x1 - x2) + abs(y1 - y2)\n",
    "        \n",
    "        if len(points) < 2:\n",
    "            return 0\n",
    "\n",
    "        n = len(points)\n",
    "        edge = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    heapq.heappush(edge[i], [10 ** 9, j])\n",
    "                    # edge[i].append([10 ** 9, j])\n",
    "                else:\n",
    "                    heapq.heappush(edge[i], [distance(points[i][0], points[i][1], points[j][0], points[j][1]), j])\n",
    "                    # edge[i].append([distance(points[i][0], points[i][1], points[j][0], points[j][1]), j])\n",
    "\n",
    "        flag = 10 ** 9\n",
    "        temp = [0, 0]\n",
    "        for i in range(n):\n",
    "            if edge[i][0][0] < flag:\n",
    "                flag = edge[i][0][0]\n",
    "                temp = [i, edge[i][0][1]]\n",
    "\n",
    "        res = flag\n",
    "        visited = set(temp)\n",
    "        heapq.heappop(edge[temp[0]])\n",
    "        heapq.heappop(edge[temp[1]])\n",
    "        while len(visited) < n:\n",
    "            flag = 10 ** 9\n",
    "            temp = -1\n",
    "            for v in visited:\n",
    "                while len(edge[v]) > 0 and edge[v][0][1] in visited:\n",
    "                    heapq.heappop(edge[v])\n",
    "                if edge[v][0][0] < flag:\n",
    "                    flag = edge[v][0][0]\n",
    "                    temp = v\n",
    "            # print(edge, visited, flag, temp)\n",
    "            res += edge[temp][0][0]\n",
    "            visited.add(edge[temp][0][1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        # kruskal union find\n",
    "        parents = [i for i in range(len(points))]\n",
    "\n",
    "        def find(i):\n",
    "            if parents[i] != i:\n",
    "                parents[i] = find(parents[i])\n",
    "            return parents[i]\n",
    "\n",
    "        def union(i, j):\n",
    "            rootI = find(i)\n",
    "            rootJ = find(j)\n",
    "            if rootI == rootJ:\n",
    "                return False\n",
    "            parents[rootI] = rootJ\n",
    "            return True\n",
    "\n",
    "        edges = []\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(points)):\n",
    "                if i != j:\n",
    "                    distance = abs(points[i][0]-points[j][0]) + abs(points[i][1] - points[j][1])\n",
    "                    edges.append((i, j, distance))\n",
    "        \n",
    "        edges.sort(key=lambda e: e[2])\n",
    "        cost = 0\n",
    "        edge_num = 0\n",
    "        for e in edges:\n",
    "            if union(e[0], e[1]):\n",
    "                cost += e[2]\n",
    "                edge_num += 1\n",
    "                if edge_num == len(points)-1:\n",
    "                    break\n",
    "        return cost\n",
    "#         n = len(points)\n",
    "#         uf = UnionFind(n)\n",
    "#         edges = []\n",
    "#         for i in range(n):\n",
    "#             for j in range(i+1, n):\n",
    "#                 point_i = points[i]; point_j = points[j]\n",
    "#                 dis_ij = abs(point_i[0] - point_j[0]) + abs(point_i[1] - point_j[1])\n",
    "#                 edges.append((dis_ij, i, j))\n",
    "                \n",
    "#         edges.sort()\n",
    "#         N = 0; cost = 0\n",
    "#         for cost_ij, point_i, point_j in edges:\n",
    "            \n",
    "#             if uf.find(point_i) != uf.find(point_j):\n",
    "#                 uf.union(point_i, point_j)\n",
    "#                 cost+=cost_ij\n",
    "#                 N+=1  \n",
    "#                 if N == n-1:\n",
    "#                     break\n",
    "                \n",
    "#         return cost\n",
    "\n",
    "# class UnionFind:\n",
    "#     def __init__(self, size):\n",
    "#         self.root = [i for i in range(size)]\n",
    "#         self.rank = [1] * size\n",
    "#     def find(self, x):\n",
    "#         if x == self.root[x]:\n",
    "#             return x\n",
    "#         self.root[x] = self.find(self.root[x])\n",
    "#         return self.root[x]\n",
    "#     def union(self, x, y):\n",
    "#         rootX = self.find(x)\n",
    "#         rootY = self.find(y)\n",
    "#         if rootX != rootY:\n",
    "#             if self.rank[rootX] > self.rank[rootY]:\n",
    "#                 self.root[rootY] = rootX\n",
    "#             elif self.rank[rootX] < self.rank[rootY]:\n",
    "#                 self.root[rootX] = rootY\n",
    "#             else:\n",
    "#                 self.root[rootX] = rootY\n",
    "#                 self.rank[rootY] += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        edge_list = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                edge_list.append((abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), i, j))\n",
    "        edge_list.sort(key=lambda x:x[0])\n",
    "\n",
    "        fa_list = [i for i in range(n)]\n",
    "        \n",
    "        def find(x):\n",
    "            if x == fa_list[x]:\n",
    "                return x\n",
    "            else:\n",
    "                fa_list[x] = find(fa_list[x])\n",
    "                return fa_list[x]\n",
    "        \n",
    "        def merge(x, y):\n",
    "            fa_list[find(x)] = find(y)\n",
    "        \n",
    "        ans = n_len = 0\n",
    "        for d, i, j in edge_list:\n",
    "            if find(i) == find(j):\n",
    "                continue\n",
    "            merge(i, j)\n",
    "            n_len += 1\n",
    "            ans += d\n",
    "            if n_len == n - 1:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        graph = [list() for _ in range(n)]\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                graph[i].append([abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1]), j])\n",
    "                graph[j].append([abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1]), i])\n",
    "        \n",
    "        heap = [(0, 0)] #(weight, to)\n",
    "        mst = set()\n",
    "        weight = 0\n",
    "        while heap:\n",
    "            point = heapq.heappop(heap)\n",
    "            if point[1] not in mst:\n",
    "                mst.add(point[1])\n",
    "                weight += point[0]\n",
    "                for item in graph[point[1]]:\n",
    "                    heapq.heappush(heap, item)\n",
    "            if len(mst) == n:\n",
    "                return weight"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        # kruskal union find\n",
    "        # class UF:\n",
    "        #     def __init__(self, n):\n",
    "        #         self.parents = [i for i in range(n)]\n",
    "            \n",
    "        #     def find(self, i):\n",
    "        #         if self.parents[i] != i:\n",
    "        #             self.parents[i] = self.find(self.parents[i])\n",
    "        #         return self.parents[i]\n",
    "            \n",
    "        #     def union(self, i, j):\n",
    "        #         rootI = self.find(i)\n",
    "        #         rootJ = self.find(j)\n",
    "        #         if rootI == rootJ:\n",
    "        #             return False\n",
    "        #         self.parents[rootI] = rootJ\n",
    "        #         return True\n",
    "        parents = [i for i in range(len(points))]\n",
    "\n",
    "        def find(i):\n",
    "            if parents[i] != i:\n",
    "                parents[i] = find(parents[i])\n",
    "            return parents[i]\n",
    "\n",
    "        def union(i, j):\n",
    "            rootI = find(i)\n",
    "            rootJ = find(j)\n",
    "            if rootI == rootJ:\n",
    "                return False\n",
    "            parents[rootI] = rootJ\n",
    "            return True\n",
    "\n",
    "        edges = []\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(points)):\n",
    "                if i != j:\n",
    "                    distance = abs(points[i][0]-points[j][0]) + abs(points[i][1] - points[j][1])\n",
    "                    edges.append((i, j, distance))\n",
    "        \n",
    "        edges = sorted(edges, key=lambda e: e[2])\n",
    "        cost = 0\n",
    "        for e in edges:\n",
    "            if union(e[0], e[1]):\n",
    "                cost += e[2]\n",
    "        \n",
    "        return cost\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        if len(points)==1:return 0\n",
    "        self.graph={}\n",
    "        #n=len(points)\n",
    "        for i,p in enumerate(points):\n",
    "            for j in range(i+1,len(points)):\n",
    "                if i not in self.graph:\n",
    "                    self.graph[i] = []\n",
    "                if j not in self.graph:\n",
    "                    self.graph[j] = []\n",
    "                self.graph[i].append((j,abs(p[0]-points[j][0])+abs(p[1]-points[j][1])))\n",
    "                self.graph[j].append((i,abs(p[0]-points[j][0])+abs(p[1]-points[j][1])))\n",
    "\n",
    "\n",
    "        visited = set()\n",
    "        min_heap = [(0, 0)]  # 使用最小堆来选择最短边\n",
    "        #print(self.graph)\n",
    "        total_cost=0\n",
    "        while min_heap:\n",
    "            cost, current_vertex = heapq.heappop(min_heap)\n",
    "\n",
    "            # 如果顶点已访问过，则跳过\n",
    "            if current_vertex in visited:\n",
    "                continue\n",
    "\n",
    "            # 标记顶点为已访问\n",
    "            visited.add(current_vertex)\n",
    "            total_cost+=cost\n",
    "\n",
    "            # 打印或处理当前边\n",
    "            #print(f\"Add edge to MST: {current_vertex}\")\n",
    "\n",
    "            # 将相邻未访问的顶点加入最小堆\n",
    "\n",
    "            for neighbor, weight in self.graph[current_vertex]:\n",
    "                if neighbor not in visited:\n",
    "                    heapq.heappush(min_heap, (weight, neighbor))\n",
    "\n",
    "    \n",
    "        return total_cost\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        dist = lambda x, y: abs(x[0] - y[0]) + abs(x[1] - y[1])\n",
    "        edges = defaultdict(list)\n",
    "        n = len(points)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                dis = dist(points[i], points[j])\n",
    "                edges[i].append([j, dis])\n",
    "                edges[j].append([i, dis])\n",
    "        qu = [(0, 0)]\n",
    "        heapq.heapify(qu)\n",
    "        vi = set()\n",
    "        res = 0\n",
    "        while len(vi) < n:\n",
    "            c, u = heapq.heappop(qu)\n",
    "            if u in vi:\n",
    "                continue\n",
    "            vi.add(u)\n",
    "            res += c \n",
    "            for v, nc in edges[u]:\n",
    "                if v not in vi: \n",
    "                    heapq.heappush(qu, (nc, v))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        distes = []\n",
    "\n",
    "        for i in range(n):\n",
    "            xi, yi = points[i]\n",
    "            for j in range(i+1, n):\n",
    "                xj, yj = points[j]\n",
    "                dist = abs(xj - xi) + abs(yj - yi)\n",
    "                distes.append([i, j, dist])\n",
    "                distes.append([j, i, dist])\n",
    "\n",
    "        distes = sorted(distes, key=lambda x: x[2])\n",
    "        \n",
    "        selected_nodes = [0]\n",
    "        unselected_nodes = [i for i in range(1, n)]\n",
    "\n",
    "        ret = 0\n",
    "        while len(unselected_nodes) > 0:\n",
    "            for can in distes:\n",
    "                i, j, dist = can\n",
    "                if i in selected_nodes and j in unselected_nodes:\n",
    "                    ret += dist\n",
    "                    selected_nodes.append(j)\n",
    "                    idx = unselected_nodes.index(j)\n",
    "                    unselected_nodes = unselected_nodes[:idx] + unselected_nodes[idx+1:]\n",
    "                    break\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        def dist(x, y):\n",
    "            return abs(x[0] - y[0]) +  abs(x[1] - y[1])\n",
    "        #kruscal\n",
    "        adj_matrix = [[] for _ in range(n)]\n",
    "    \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i==j: \n",
    "                    continue\n",
    "                dist_ij = dist(points[i], points[j])\n",
    "                adj_matrix[i].append((dist_ij, i, j))\n",
    "                #adj_matrix[j].append((dist_ij, j, i))\n",
    "        cost = 0\n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "        mindist_edge = adj_matrix[0]\n",
    "        heapify(mindist_edge)\n",
    "        min_edge = []\n",
    "        while mindist_edge:\n",
    "            min_v, x, min_n = heappop(mindist_edge)\n",
    "            if  min_n not in visited:\n",
    "                cost += min_v\n",
    "                visited.add(min_n)\n",
    "                for z, x,y in adj_matrix[min_n]:\n",
    "                    if y not in visited:\n",
    "                        heappush(mindist_edge, (z, x, y))\n",
    "        return cost\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        n=len(points)\n",
    "        arr=[]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j:\n",
    "                    x,y=points[i]\n",
    "                    x1,y1=points[j]\n",
    "                    d=abs(x-x1)+abs(y-y1)\n",
    "                    arr.append([d,i,j])\n",
    "        p={i:i for i in range(n)}\n",
    "        def find(x):\n",
    "            if p[x]==x:\n",
    "                return p[x]\n",
    "            p[x]=find(p[x])\n",
    "            return p[x]\n",
    "        def union(x,y):\n",
    "            p[find(x)]=find(y)\n",
    "        arr.sort()\n",
    "        cnt=0\n",
    "        for c,s,e in arr:\n",
    "            a=find(s)\n",
    "            b=find(e)\n",
    "            if a!=b:\n",
    "                union(s,e)\n",
    "                cnt+=c\n",
    "        return cnt \n",
    "\n",
    "      \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
